/*
    XTU OJ: 1375
    by: fifth_light
*/

#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>
#include <limits.h>


#define MAX_LIMIT 1000000000
int fibonacci_count = 0;
int64_t fibonacci[100];
void calc_fibonacci() {
    fibonacci[0] = 1;
    fibonacci[1] = 2;
    for (int i = 2; i < 100; i++) {
        fibonacci[i] = fibonacci[i - 1] + fibonacci[i - 2];
        if (fibonacci[i] > MAX_LIMIT) {
            fibonacci_count = i;
            break;
        }
    }
    // printf("last: index=%d value=%" PRId64 "\n", fibonacci_count, fibonacci[fibonacci_count]);
}

int equal_count(int a, int b, int c) {
    if ((a == b) && (b == c)) {
        return 2;
    } else if ((a == b) || (b == c) || (a == c)) {
        return 1;
    } else {
        return 0;
    }
}

int main(void) {
    calc_fibonacci();
    int t;
    scanf("%d", &t);
    for(int i = 0; i < t; i++) {
        int64_t num;
        scanf("%" SCNd64, &num);
        
        int results[3] = {0};
        for (int i = 0; i < fibonacci_count; i++) {
            for (int j = 0; j < fibonacci_count; j++) {
                for (int k = 0; k < fibonacci_count; k++) {
                    if (num == fibonacci[i] + fibonacci[j] + fibonacci[k]) {
                        results[equal_count(i, j, k)]++;
                    }
                }
            }
        }
        
        int count = results[0] / 6 + results[1] / 3 + results[2];
        printf("%d\n", count);
    }
    return 0;
}
